package com.niuke;

import javax.print.attribute.standard.OrientationRequested;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-16 01:15:08
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-16     张李鑫                     1.0         1.0 Version
 */
public class JZ8 {
    public static class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }


    }

    /**
     * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
     * 下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
     */

    public static TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode.right != null) {
            TreeLinkNode cur = pNode.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        } else if (pNode.next == null) {
            return null;
        } else {
            TreeLinkNode next = pNode.next;
            if (next.left == pNode) {
                return next;
            } else {
                TreeLinkNode cur = pNode;
                while (next.next != null) {
                    cur = next;
                    next = next.next;
                }
                return cur == next.right ? null : next;
            }
        }
    }

    public static void main(String[] args) {
        TreeLinkNode treeLinkNode = new TreeLinkNode(1);
        TreeLinkNode treeLinkNode1 = new TreeLinkNode(2);
        TreeLinkNode treeLinkNode2 = new TreeLinkNode(3);
        TreeLinkNode treeLinkNode3 = new TreeLinkNode(4);

        treeLinkNode.left = treeLinkNode1;
        treeLinkNode1.next = treeLinkNode;

        treeLinkNode1.right = treeLinkNode2;
        treeLinkNode2.next = treeLinkNode1;

        treeLinkNode3.next = treeLinkNode2;
        treeLinkNode2.right = treeLinkNode3;

        TreeLinkNode treeLinkNode4 = GetNext(treeLinkNode3);
        System.out.println(treeLinkNode4);
    }
}